2024 iThome 鐵人賽

DAY 2

佛心分享-刷題不只是刷題

刷題小白與Python的動態規劃之旅系列第 2 篇

Day 02 動態規劃簡介

16th鐵人賽 python leetcode dynamic programming

hinalove

2024-09-16 22:33:45

81 瀏覽

分享至

何謂動態規劃

實際上，與其說動態規劃是一個演算法，不如說其描述的是「一群演算法」背後共通的拆解邏輯更為恰當。動態規劃的核心概念分為兩個部分：

將複雜的母問題拆解為互相嵌套的子問題，透過求解較小的子問題，來進一步推演得到母問題的答案。

有基礎演算法概念的話，若只看這部分，其實就是「分治法」(Divide and Conquer)。
有大量的子問題會被重複問到，將已計算過的答案記錄下來，不再重複計算。以少量的空間換取時間。

分治法所拆分出的子問題解答，思考如何對其「紀錄與重用」，可謂動態規劃中最重要的概念。

綜合以上兩點，動態規劃也可謂一種對於「遞迴算法」的優化。在本系列後半段深入Medium、Hard難度時，我們在分析題目的階段也會經常從遞迴算法切入，再思考如何用動態規劃來降低複雜度。

儘管動態規劃的題型非常多、甚至連解法也完全不同(所以才會說動態規劃是「一類」演算法的總稱)，但是背後最重要的共通思維，便是對問題的「分治」以及對解答的「重用」。希望讀著跟著本系列解題時，能去感受每個解法中的這兩大重點，定能有所收穫。

適用動態規劃的問題

動態規劃只能用於「最佳子結構問題」。

所謂的最佳子結構問題，指的是「能夠基於局部最佳解，來決定全局最佳解」(有些題目需要照特定的順序求解，或者僅能求近似值)。

因為動態規劃基於分治法，必須先解出某個局部，再由每個局部的答案來解更大的局部，因此這些局部必須要彼此獨立(或者至少，能照特定的順序求解)。
無後效性

子問題的解一旦能夠決定，就不再改變，亦不受到更大、包含該子問題的問題的求解策略的影響。

舉個簡單的反例，如19路圍棋，由於棋盤上任意局部的情勢都會影響整體情勢(非最佳子結構問題)，且後續的落子會持續影響、改變雙方盤面上棋子的死活(有後效性)，故無法僅用動態規劃演算法來求解。
子問題重疊性質

若子問題並沒有高度重疊，就是普通的遞迴算法。當子問題並不會被多次求解，額外花費空間紀錄子問題的解答就沒有意義。

舉例來說，像是在二元搜尋法(終極密碼、猜數字問題)當中，我們並不需要紀錄那些已被排除的範圍，只需要持續關注答案數字可能範圍的上下界即可。此時用動態規劃，就只是殺雞用牛刀，反而增加解題的成本。

從「費氏數列」學動態規劃的兩個策略

中學時代一定解過這個問題：

給定一個數列：

第0項為0 (此處照程式語言的習慣，稱首項為第0項)

第1項為1

剩下的項均遵守規則：每一項均為前一項、前前一項之和。

換言之：對所有n>=2，F(n) = F(n-1) + F(n-2)

求本數列的第K項

Leetcode 509. Fibonacci Number 是完全相同的問題

或許你會認為這個問題十分簡單，似乎不需用到動態規劃呀！其實在中學的解法中，我們(的老師)很直覺地就應用了一維動態規劃的技巧(1-D DP)。

先來檢驗一下本題是否能用(且適合用)動態規劃求解吧！

可以分治(最佳子結構問題)

對於任意的第K項，只要先知道第K-1和第K-2項，就必定能解出。
無後效性

任何一項的值都只受到其「前面」項的值影響。
子問題重疊性質

若我們用遞迴演算法的思維來分析，會發現需要不斷重複求解較小項數的值。

舉例而言，若母問題求第10項的值F(10) = F(9) + A(8)(這裡我故意將兩個子問題用不同符號表示)

需要先求第9項的值F(9) = F(8) + F(7)

也需要求第8項的值A(8) = A(7) + A(6)

到這裡就發現問題大條了，光是第八項，就被問了兩次(F(8)與A(8))，且這個兩次都還會再各自被分治成更小的問題。越前面的項次(越小的問題)，就被問越多次，無形之中浪費了大量的時間。

簡單分析可知，費氏數列的問題，需要且適合用動態規劃演算法來求解。

之所以一直強調要討論「適合」性，是因為在某些特定題型下，遞迴演算法除了常用動態規劃演算法來優化，也可能使用貪婪策略(Greedy Strategy)。由於後者的時間複雜度大多比動態規劃演算法更加的優秀(更加節省時間)，故一股腦往DP的方向去思考並不是很好的解題習慣。常用的工具，就要盡可能的多。

暴力解(簡單遞迴)

我們先以Python3來實作暴力解，再和DP解來比較時間複雜度。

範例程式碼：

from timeit import timeit

def fib(n):          # 求解第 n 項
    if n==0:         # 第 0 項 == 0
        return 0
    elif n==1:       # 第 1 項 == 1
        return 1
    else:
        return fib(n-1) + fib(n-2) # 遞迴式

# 求第10、20、30項，分別重複執行100次，取其時間(s)

print(timeit(lambda: fib(10), number=100)) #  0.002084
print(timeit(lambda: fib(20), number=100)) #  0.443784
print(timeit(lambda: fib(30), number=100)) # 46.923292

註解的數字是我在repl上面執行的結果。

由於timeit還會受到執行環境、資源釋放...等額外因素的影響，這邊我們只觀察數量級的變化。

可以發現，當計算的項次線性的增加，執行時間卻呈指數的增加。顯然，由於對子問題的重複求解，浪費了大量的時間在計算已經算過的答案，造成時間的浪費。

對費氏數列簡單遞迴求解的時間複雜度為糟糕的 指數時間

O(φ^n) (φ=黃金比例1.618)

詳細的數學證明較為複雜不在本系列範圍，簡單補充如下：

對任一項往下遞迴的「總分支數」會正比於該項的值，因此求解某項的時間複雜度，亦正比於該項的值

當n較大時，費氏數列相鄰兩項的比值為φ

Bottom-up DP：中學遞迴數列算法

回顧一下中學時老師給出的簡單算法：用數列的規則來推理，從第2項開始，一項接著一項往後算。

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3

...依此類推。

乍看之下會覺得，這和前面所介紹的動態規劃策略毫無相關？

但實際上，當我們要計算第4項時，要「用到」第3、第2項的值。

這就是前述的「重用」子問題答案。

當我們(人)在紙上推演時，很自然的記錄下這些算過的項次，但對電腦來說，也要使用額外的程式碼來「紀錄」這些子問題答案。

若將整個解題過程抽象化，可以整理如下：

得出最小子問題的答案

即F(0)與F(1)
得出狀態轉移式：描述如何從小的問題答案求解大的問題答案，的(類似)遞迴關係式

即 F(n) = F(n-1) + F(n-2)

a.k.a 分治法
找到合適的計算順序，逐步計算並記錄答案

即從n=2一路往上算出每一項

a.k.a 記錄與重用
得到母問題的答案

由於費氏數列是個簡單的1-D DP問題，前述步驟1~3都不用想就完成了，但對於較複雜的DP問題，如何實現步驟1~3就相當仰賴經驗與直覺。

照著前述流程，從最小子問題開始逐步推演至母問題答案的過程(策略)，稱為Buttom-up Dynamical Programminng

範例程式碼：

from timeit import timeit

def fib(n):  # 根據合適的計算順序從小，計算並記錄答案 
    fibs = [0,1]                    # 最小子問題
    for i in range(2,n+1):          # 狀態轉移式
        fibs.append(fibs[i-1] + fibs[i-2])
    return fibs[n]                  # 解出母問題

# 求第10、20、30項，分別重複執行10000次，取其時間(s)

print(timeit(lambda: fib(10), number=10000)) #  0.0136
print(timeit(lambda: fib(20), number=10000)) #  0.0387
print(timeit(lambda: fib(30), number=10000)) #  0.0459

可以發現，因為我們對每一項僅求解1次，且求解所花的時間為常數，故變成線性的增長了。

Bottom-up DP求解費氏數列的時間複雜度為 線性時間

O(n)

Top-Down DP：遞迴算法的優化

回到一開始的遞迴算法，能否對其優化，來規避掉重複計算子問題的浪費呢？

其實很簡單，我們只需要：

建立一個dict
在每次fib函式計算結束時，就將參數作為key，回傳值作為value，存進這個dict
在每次要調用fib函式之前，都先去查看一下dict中有沒有儲存這個引數，若有，就直接回傳答案，不去調用fib，如此一來，對於相同的引數(a.k.a.相同的子問題)，就不會重複計算了。

前幾次寫會比較不習慣，可以多注意以下的重點：

實作的重點，在於對答案的「快取」，也就是將「參數-答案」作為key-value pair，存入HashMap(以Python來說是dict)，並且在「調用函數之前」先查值，查無才進行呼叫，查有就直接取值(取出算過的答案)。

因為本例要計時，才使用Class來實作，刷題時可以用比較簡單的function代替，或者直接放大絕(見後述cache裝飾子)

範例程式碼：

from timeit import timeit

class Fib():
    def __init__(self, n):
        self.ans = {0: 0, 1: 1} # 用來記錄答案
        self.fill(n)            # 遞迴求解第n項
        self.value = self.ans[n]# 取出最終答案
    def fill(self, k):
        if k in self.ans:       # 如果已經算過這項
            return self.ans[k]  # 直接告訴我這一項
                                # 沒算過才算(遞迴式)
                                # 算好記得也把答案存進去dict裡面
        self.ans[k] = self.fill(k - 1) + self.fill(k - 2)
        return self.ans[k]      # 找答案
        

print(timeit(lambda:Fib(10).value, number=10000)) # 0.11924
print(timeit(lambda:Fib(20).value, number=10000)) # 0.10880
print(timeit(lambda:Fib(30).value, number=10000)) # 0.17843

從上例可以發現，這個算法和一開始的遞迴算法完全相同，只多了一個快取答案的步驟。

將過程抽象化，可以分解為：

得出最小子問題的答案

即F(0)與F(1)
得出遞迴關係式：描述如何從小的問題答案求解大的問題答案，的(類似)遞迴關係式

即 F(n) = F(n-1) + F(n-2)

a.k.a 分治法
設計快取，用來記錄答案

a.k.a 記錄與重用
遞迴計算母問題的答案求解F(n)

照著前述流程，從母問題開始逐步向下遞迴至最小子問題的過程(策略)，稱為Top-Down Dynamical Programminng

分析實驗的時間，可以發現，雖然算法的核心完全沒有任何改變，就是一開始的遞迴算法，但我們利用快取阻止了所有重複計算的遞迴分支，每個參數(a.k.a.每一項)只計算一次，故時間優化成線性的增長。

透過Top-Down DP求解費氏數列的時間複雜度為線性時間

O(n)

兩種策略的相同點

若比較前述兩種DP的策略，可以發現：

雖然程式碼運作的方向相反，但實際計算的方向相同，都是從小問題往大問題計算。

以費氏數列為例，實際上都是先算出前面的項次，才去計算後面的項次。
都需要得到最小子問題的答案

以費氏數列為例，都需要已知F(0)與F(1)
都需思考「如何從小問題的答案求解大問題」(分治法)
- 對於 Bottom-up DP，我們稱之為狀態轉移式
- 對於 Top-Down DP，我們稱之為遞迴關係式
都需要記錄並重用過程中子問題的答案
- 對於 Bottom-up DP，常使用陣列
  
  (以Python來說是list)
- 對於 Top-Down DP，需要對函式的參數與回傳值做快取
  
  (以Python來說，可以用dict手刻，或者用@cache黑魔法)

至於相異點，等本系列文多寫幾題不同類型的DP，會再來做異同的比較。

建議各位讀者在本系列文Easy題的階段，盡量多練習兩種相反的策略，會感受到各自有適用的情境。

Bottom-up 的好幫手：@cache

在實作 Top-Down DP時，如果懶得手刻快取(記錄答案)，可以這樣寫：

from timeit import timeit
from functools import cache

@cache           # 對原本的遞迴函式加上@cache裝飾子
def fib(n):          
    if n==0:         
        return 0
    elif n==1:       
        return 1
    else:
        return fib(n-1) + fib(n-2) 

# 求第10、20、30項，分別重複執行100次，取其時間(s)

print(timeit(lambda: fib(10), number=10000)) # 0.0012
print(timeit(lambda: fib(20), number=10000)) # 0.0013
print(timeit(lambda: fib(30), number=10000)) # 0.0012

因為本範例沒有清除緩存，所以fib(20)實際上只計算了11~20項。

可以發現：我們只是在一開始的遞迴函式前面加上@cache就實現了前述Top-Down DP，再也不用自己寫快取了，好耶！

關於裝飾子與@cache如何運作，因為並非本系列重點，若有興趣可以參考以下文章連結。

Medium: Decorator

官方文檔：functools

狀態、維度與轉移式

狀態

無論採用Top-Down或者Bottom-Up策略，解題的關鍵在於想出「要計算什麼」，也就是說，使用分治法將母問題往下拆分成子問題時，如何正確描述我們要解的每一個子問題。

我們使用「狀態」(state)來描述每一個子問題。

以本文舉例的「求解費氏數列第n項」來說，分治法告訴我們，每一個小的子問題，就是「算出從第0~n項中的每一項」。

換言之，子問題可描述為：求費氏數列的第k項，0<=k<=n

維度

當我們描述一個問題，至少需要用到一組參數(例如本題，用到了k)，就稱為一維(1-D DP)。若至少需要用到兩組參數，就稱為二維(2-D DP)。

掌握動態規劃的維度，對於解題是很重要的，因為這讓我們能掌握演算法的時間、空間複雜度，也能藉此思考有沒有優化的空間。

狀態轉移式(遞迴關係式)

而如何使用更小的子問題答案，來求解這個子問題的答案，這樣的過程我們就用狀態轉移式(遞迴關係式)來表示。

以費氏數列為例，狀態轉移式就是數列的規則 F(k) = F(k-1) + F(k-2)

在設計動態規劃時，一定要先得到正確的轉移式。

對於Top-Down 策略來說，得出轉移式，就可以照搬寫出遞迴函式。
對於Bottom-up 策略來說，轉移式還提示了正確的計算順序。
對於較複雜、需要進一步優化的問題，從轉移式中尋找冗餘的部分，通常能找到優化的線索。

複雜度分析

DP時間複雜度

對於較單純的DP，時間複雜度 = 狀態轉移數 x 計算複雜度

狀態轉移數指：需要算出的狀態總數。對於維度越高的DP，所需要計算的總狀態數就會以相乘的方式增長。

計算複雜度指的是，「計算狀態轉移的過程」本身的時間複雜度。

以本文所舉的費氏數列為例：

為1-D DP，狀態轉移數 = 要算的項數 = n，因此為線性時間 O(n)
計算複雜度：僅做簡單的加法，因此為常數時間 O(1)
因此，總時間複雜度為 O(n) x O(1) = O(n)

對於較複雜的DP題，要求出精確的時間複雜度公式可能非常複雜，如果不是為了程式競賽、學校考試等較深入的問題，單純以面試為目標，可以先掌握大概的數量級即可。例如，介於O(n^2)到O(n^3)之間。

DP空間複雜度

DP的空間複雜度取決於「需要持續紀錄的狀態數」。

注意這並不一定等同狀態轉移數，因為根據計算順序，有些被計算過的問題的答案，可能不再需要用到，此時清除這些不需要的空間，就能優化空間複雜度。

以費氏數列為例，原本空間複雜度等同總項數n，但實際上，當我們進行Bottom-up策略時，只需要讓電腦記住最後的兩項即可往後計算。因此，可將空間複雜度縮減至常數。範例程式碼如下：

def fib(n):
    pprev = 0
    prev = 1
    for _ in range(2,n+1):
        (pprev, prev) = (prev, pprev + prev)
    return prev

print(fib(10)) // 55

此法稱為滾動式DP，通常空間上能省一個維度。

使用Bottom-up策略時，當我們對於狀態轉移式、計算順序掌握得越清楚，就能找到節省空間的方法。

而Top-Down策略，因為計算的順序是由遞迴函式控制，通常較沒有空間優化的機會。此外，遞迴函式本身的callstack也會佔據空間。

因此當狀態緊密時，雖然複雜度相同，但是Top-Down策略通常會有較大的常數。

通常刷題時比較容易卡在時間(TLE)，空間的優化有個概念就好，不一定會去實作它。

總結

DP不算是一個特定的演算法，而是類似分治法的一種「演算法策略」，由於用途、寫法多變，甚至還能在狀態轉移式的計算中結合其他的資料結構或者演算法進行優化，因此可謂易學難精。只能靠多看題目、多練習，並且在刷題時，盡量自己設計狀態、列轉移式，再算複雜度、最後用程式碼實作出來，系統性的去掌握DP的流程，如此一來，至少在看到題目時能夠快速判斷能否DP、怎麼DP。

本文簡介了DP的基本概念，兩種殊途同歸的策略，以及分析題目時常見的專有名詞。明天起，我們就要正式挑戰LeetCode上的Eazy題了！

以上為Day2的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。